The present invention relates to a method of calculating Fast Fourier Transform (FFT) and to a device for carrying out the method, and in particular to the interconnection of and the coaction between the calculating unit and the memory of said device.
The Discrete Fourier Transform (DFT) of a sequence f(n) is defined as:       X    ⁡          (      k      )        =            ∑              n        =        0                    N        -        1              ⁢                  x        ⁡                  (          n          )                    ⁢                        W          kn                ⁡                  (                                    n              =              0                        ,            1            ,            …            ⁢                          xe2x80x83                        ,                          N              -              1                                )                    
where the weight coefficient W=exe2x88x9212xcfx80/N.
The inverse to the Discrete Fourier Transform is defined as       x    ⁡          (      n      )        =            1      N        ⁢                  ∑                  k          =          0                          N          -          1                    ⁢                        X          ⁡                      (            k            )                          ⁢                              W            kn                    ⁡                      (                                          k                =                0                            ,              1              ,              …              ⁢                              xe2x80x83                            ,                              N                -                1                                      )                              
where the weight coefficient W=exe2x88x9212xcfx80/N.
If X(k) or x(n) is calculated directly in accordance with the definitions, the number of additions will be N(Nxe2x88x921) and the number of multiplications will be generally in the order of magnitude of N2.
In 1965, Cooley and Tukey introduced a novel method of calculating X(k) and x(n) respectively, resulting in a much shorter calculation time. The method was designated Fast Fourier Transform (FFT) and utilizes the circumstance that the same calculations reoccur at several positions. The number of additions and multiplications can be reduced to the order of log2N when N is a two-power.
In brief, the method is based on a number of successive calculations with a series or column of values, where each pair of calculations is called a butterfly.
This gives a new column of N number of values. These are used for new, similar calculations and give, in turn, a new column of N number of values and so on, until log2 N columns have been calculated, the answer being given by the last series. This method can be varied in a number of different ways.
The old series is no longer required each time a new series is calculated. This enables the memory, or store, in which the previous series is stored to be reused, this being referred to as calculating inplace. Thus, the method can be carried out with a memory of size N, disclosed in GB 1 546 173 and GB 2 006 485, for instance. The drawback with this is that memory accesses are always made to the same memory, which is not particularly effective.
FFT can also be implemented with the use of two memories of size N, as disclosed in the technical report xe2x80x9cAn Energy-Efficient FFT Processor Architecturexe2x80x9d (NGT-70340-1994-1), Department of Electrical Engineering, Stanford University, Stanford, Calif., U.S.A. Data is read from one memory, processed and then written into the other memory. This method is faster than calculating inplace, since writing and reading can take place simultaneously. The drawback with this method is that it requires twice as much memory as the FFT to be calculated.
The present invention addresses the problem of FFT calculations requiring either a great deal of time or a large amount of memory space.
The object of the present invention is to provide a solution to this problem by organizing the interconnection and coaction between the calculating unit and memory, so as to enable two butterfly calculations to be commenced simultaneously. This is achieved by reading the input values from memory positions in the memories and intermediately storing these input values in a register in the calculating unit after reading, and/or by storing the output values to be written into memory positions in the memory intermediately in a register in the calculating unit prior to writing-in said values. The values are conveniently allocated or distributed so that each memory will contain essentially the same number of values. This enables, for instance, two memories to be used to a maximum, by reading from and writing into memory positions in the two memories simultaneously. Alternatively, values can be read from one memory at the same time as values are written into the other memory.
One advantage afforded by the present invention is that the memories are utilized to a maximum, therewith enabling the memory space to be minimized to half the memory space required by the known solution that utilizes two memories. Another advantage is that the time required in this respect can be reduced in comparison with the time required by the known solution that utilizes a single memory.
The invention will now be described in more detail with reference to preferred embodiments thereof and also with reference to the accompanying drawings. In the following text, a butterfly designates a group of least two calculations, where each calculation includes at least one calculation step.